"""
Argumentation Framework module

author: Mikolaj Podlaszewski <mikolaj.podlaszewski@gmail.com>
changes:
  02 Nov 2009 first version
  18 Nov 2009 added status function

This module implements algorithms studied during
'Computational Models of Argument' course by
prof Carminada in MICS3 program at uni.lu.
"""

class IllegalMove(Exception):
  pass

class DiscussionFinished(Exception):
  pass

class Discussion:
  PROPONENT = 0
  OPPONENT  = 1
  def __init__(self, frame):
    self._framework = frame
    self.legal_moves = set(frame.ar.values())
    self.arguments = []
    self.turn = Discussion.PROPONENT
    self.winner = None
  def __str__(self):
    return '[%s]' % ', '.join([str(a) for a in self.arguments])
  def __copy__(self):
    result = self.__class__(self._framework)
    result.legal_moves = set(self.legal_moves)
    result.arguments = self.arguments[:]
    result.turn = self.turn
    result.winner = self.winner
    return result
  
class pDiscussion(Discussion):
  def __init__(self, frame):
    Discussion.__init__(self, frame)
    self.opponent_played = set()
    self.proponent_played = set()
    self.opponent_may_play = set()

  def __copy__(self):
    result = Discussion.__copy__(self)
    result.opponent_played = set(self.opponent_played)
    result.proponent_played = set(self.proponent_played)
    result.opponent_may_play = set(self.opponent_may_play)    
    return result
  
  def argue(self, a):
    if a not in self.legal_moves:
      raise IllegalMove()
    
    self.arguments.append(a)
    if self.turn == Discussion.PROPONENT:
      self.proponent_played.add(a)
      self.opponent_may_play |= a.minus - self.opponent_played      
      self.legal_moves = self.opponent_may_play
    else:
      self.opponent_played.add(a)
      self.opponent_may_play.remove(a)
      self.legal_moves = a.minus - self.opponent_played
      if a in self.proponent_played:
        self.winner = Discussion.OPPONENT
        self.legal_moves = set()
        raise DiscussionFinished("Proponent's move repeated by opponent.") 
    self.turn = 1 - self.turn
    
    if not self.legal_moves:
      self.winner = 1 - self.turn
      raise DiscussionFinished("No more moves")
    
class gDiscussion(Discussion):   
  def argue(self, a):
    if a not in self.legal_moves:
      raise IllegalMove()
    
    self.arguments.append(a)
    self.turn = 1 - self.turn
    if self.turn == Discussion.OPPONENT:
      self.legal_moves = a.minus
    else:
      self.legal_moves = a.minus - set(self.arguments)

    if not self.legal_moves:
      self.winner = 1 - self.turn
      raise DiscussionFinished("No more moves")


def s2s(s):
  """convert set to string"""
  return "{%s}" % ", ".join([str(x) for x in s])

class Argument:  
  """Argument"""
  _framework = None
  name = ''
  plus, minus = None, None
  def __init__(self, frame, name):
    self._framework = frame
    self.name = name
    self.plus = set()
    self.minus = set()
  def __str__(self):
     return self.name

class Labelling:
  """Labelling"""
  _framework, IN, OUT, UNDEC = None, None, None, None
  def __init__(self, frame, IN = set(), OUT = None, UNDEC = None):
    self._framework = frame
    self.IN = IN
    self.OUT = OUT
    self.UNDEC = UNDEC
    if self.UNDEC == None:
      self._update_UNDEC()
  
  def _update_UNDEC(self):
    """Updates UNDEC so that it contains arguments not present in IN and OUT"""
    self.UNDEC = set(self._framework.ar.values())
    self.UNDEC.difference_update(self.IN, self.OUT)
    
  def __str__(self):
    return "{{%s},{%s},{%s}}" % (
      ', '.join([a.name for a in self.IN]),
      ', '.join([a.name for a in self.OUT]),
      ', '.join([a.name for a in self.UNDEC]))
      
  def idStr(self):
    """Returns unique string representation IN|OUT where IN and OUT arguments are serted alpabetically"""
    IN = [a.name for a in self.IN]
    IN.sort()
    OUT = [a.name for a in self.OUT]
    OUT.sort()
    return ''.join(IN) + '|' + ''.join(OUT)

  def getLab(self, arg):
    """Returns status of argument"""
    if arg in self.IN:
      return "IN"
    elif arg in self.OUT:
      return "OUT"
    else:
      return "UNDEC"
      
  def setLab(self, arg, status):
    self.IN.discard(arg)
    self.OUT.discard(arg)
    self.UNDEC.discard(arg)
    
    if status == "IN":
      self.IN.add(arg)
    elif status == "OUT":
      self.IN.add(arg)
    elif status == "UNDEC":
      self.IN.add(arg)
    else:
      raise Exception("Wrong status: %s" % status)

  # Predefined labellings
  @staticmethod 
  def all_IN(frame):
    """Returns all-in labelling"""
    return Labelling(frame, set(frame.ar.values()), set(), set())
  
  @staticmethod
  def all_OUT(frame):
    """Returns all-out labelling"""
    return Labelling(frame, set(), set(frame.ar.values()), set())

  @staticmethod
  def all_UNDEC(frame):
    """Returns all-out labelling"""
    return Labelling(frame, set(), set(), set(frame.ar.values()))
    
  @staticmethod
  def from_idStr(frame, s):
    """Returns labelling according to idStr"""
    (sin, sout) = s.split('|')
    IN = set()
    OUT = set()
    UNDEC = set()
    for a, ar in frame.ar.iteritems():
      if a in sin: IN.add(ar)
      elif a in sout: OUT.add(ar)
      else: UNDEC.add(ar)
    return Labelling(frame, IN, OUT, UNDEC)

  #Operations on labellings
  def intersection(self, other):
    return Labelling(self._framework, self.IN & other.IN, self.OUT & other.OUT)
    
  def intersection_update(self, other):
    self.IN &= other.IN
    self.OUT &= other.OUT
    self._update_undec()
    return self
    
  def union(self, other):
    ain = self.IN | other.IN
    aout = self.OUT | other.OUT
    return Labelling(self._framework, ain - aout, aout - ain)

  def union_update(self, other):
    self.IN |= other.IN - self.OUT
    self.OUT |= other.OUT - self.IN
    self._update_undec()
    return self

  def isLegallyOUT(self, arg):
    return arg.minus & self.IN

  def isLegallyIN(self, arg):
    return arg.minus <= self.OUT

  def is_legally_conlictfree_IN(self, arg):
    return arg.minus <= self.OUT and not arg.plus & self.IN
    
  def isLegallyUNDEC(self, arg):
    return not arg.minus & self.IN and arg.minus & self.UNDEC

  def down_admissible_update(self):
    while True:
      illigalIn = set([a for a in self.IN if not self.isLegallyIN(a)])
      illigalOut = set([a for a in self.OUT if not self.isLegallyOUT(a)])
      if not illigalIn and not illigalOut:
			  return self
      self.IN -= illigalIn
      self.OUT -= illigalOut
      self.UNDEC.update(illigalIn, illigalOut)

  def up_complete_update(self):
    while True:
      legally_IN = set([a for a in self.UNDEC if self.isLegallyIN(a)])
      legally_OUT = set([a for a in self.UNDEC if self.isLegallyOUT(a)])
      if not legally_IN and not legally_OUT:
			  return self
      self.IN |= legally_IN
      self.OUT |= legally_OUT
      self.UNDEC.difference_update(legally_IN, legally_OUT)
          
  @staticmethod  
  def SIO(labellings):
    """Sceptical initial operator"""
    return reduce(Labelling.intersection, labellings)

  @staticmethod  
  def SO(labellings):
    """Sceptical operator"""
    return Labelling.SIO(labellings).down_admissible_update()

  @staticmethod
  def CIO(labellings):
    """Credulous initial operator"""
    return reduce(Labelling.union, labellings)

  @staticmethod
  def CO(labellings):
    """Credulous operator"""
    return reduce(Labelling.union, labellings).down_admissible_update()

  @staticmethod
  def SCO(labellings):
    """Super credulous operator"""
    return reduce(Labelling.union, labellings).down_admissible_update().up_complete_update()
    
class ArgumentationFramework:
  """Argumentation Framework
     It is given by chains of attackers, different chains are separated by space
     Examples:
       ABCA - A attacks B, B attacks C, C attacks A
       ABA BCC - A attacks B, B attacks A and C, C attacks itself
  """
  ar = None
  debug = 0
  def __init__(self, desc):
    """Initialize framework"""
    self.ar = dict()
    for chain in desc.split():
      la = None
      for name in chain:
        try:
          a = self.ar[name]          
        except KeyError:
          a = Argument(self, name)
          self.ar[name] = a
        if la:
          la.plus.add(a)
          a.minus.add(la)
        la = a
        
  def __str__(self):
    """Print framework"""
    args = self.ar.values()
    args.sort(lambda a,b: cmp(a.name, b.name))    
    return "%d argument(s) in framework: %s \n\n%s\n" % (
      len(args),
      ', '.join(map(str,args)),
      "\n".join(["%s defeats: %s" %(a.name, ', '.join([b.name for b in a.plus])) for a in args]))

  def __transition_step(self, a, L):
    """Transition step"""
    if self.debug: print "Transition for %s" % str(a)
    
    IN, OUT, UNDEC = L.IN.copy(), L.OUT.copy(), L.UNDEC.copy()
    IN.remove(a)
    
    if a.minus & IN: OUT.add(a)
    else: UNDEC.add(a)

    for aa in a.plus & OUT:
      if not aa.minus & IN:
        OUT.remove(aa)
        UNDEC.add(aa)
        
    return Labelling(self, IN, OUT, UNDEC)

  def __find_stage(self, L, pot):
    """Recursive function of alghorithm"""
    
    for L2 in pot:
      if L2.UNDEC < L.UNDEC:
        return
      
    illigal_in = set(a for a in L.IN if a.minus & L.IN or a.plus & L.IN)
    if illigal_in:
        for ii in illigal_in:
          self.__find_stage(self.__transition_step(ii, L), pot)
    else:
      #check if L not present in pot (it is implementation specific because labelings are objects)
      for L2 in pot:
        if L2.IN == L.IN and L2.OUT == L.OUT and L2.UNDEC == L.UNDEC:
          return
        
      worse = set(L2 for L2 in pot if L.UNDEC < L2.UNDEC)      
      pot -= worse
      pot.add(L)
        
  def find_stage(self):
    """Returns all stage labelings of the argumentation framework"""
    pot = set()
    self.__find_stage(  Labelling.all_IN(self), pot)
    return pot
    
  def __find_semi_stable(self, L, pot):
    """Recursive function of alghorithm"""
    
    for L2 in pot:
      if L2.UNDEC < L.UNDEC:
        return
      
    illigal_in = set(a for a in L.IN if not a.minus <= L.OUT)
    if illigal_in:
      supperilligal_in = set([a for a in illigal_in if a.minus & (L.UNDEC | (L.IN - illigal_in))])
      if supperilligal_in:
        sii = supperilligal_in.pop()        
        self.__find_semi_stable(self.__transition_step(sii, L), pot)
      else:
        for ii in illigal_in:
          self.__find_semi_stable(self.__transition_step(ii, L), pot)
    else:
      #check if L not present in pot (it is implementation specific because labelings are objects)
      for L2 in pot:
        if L2.IN == L.IN and L2.OUT == L.OUT and L2.UNDEC == L.UNDEC:
          return
        
      worse = set(L2 for L2 in pot if L.UNDEC < L2.UNDEC)      
      pot -= worse
      pot.add(L)
        
  def find_semi_stable(self):
    """Returns all semi-stable labelings of the argumentation framework"""
    if self.debug: print "\n=== TRACE for find_semi_stable START ===\n"
    pot = set()
    self.__find_semi_stable(  Labelling.all_IN(self), pot)
    if self.debug: print "\n=== TRACE for find_semi_stable FINISHED ===\n"    
    return pot

  def __find_stable(self, L, pot):
    """Recursive function of alghorithm"""
    
    if len(L.UNDEC) > 0: return;
      
    illigal_in = set(a for a in L.IN if not a.minus <= L.OUT)
    if illigal_in:
      supperilligal_in = set([a for a in illigal_in if a.minus & (L.UNDEC | (L.IN - illigal_in))])
      if supperilligal_in:
        sii = supperilligal_in.pop()        
        self.__find_stable(self.__transition_step(sii, L), pot)
      else:
        for ii in illigal_in:
          self.__find_stable(self.__transition_step(ii, L), pot)
    else:
      #check if L not present in pot (it is implementation specific because labelings are objects)
      for L2 in pot:
        if L2.IN == L.IN and L2.OUT == L.OUT and L2.UNDEC == L.UNDEC:
          return        
      pot.add(L)
        
  def find_stable(self):
    """Returns all stable labelings of the argumentation framework"""
    pot = set()
    self.__find_stable(  Labelling.all_IN(self), pot)
    return pot

  def __find_prefered(self, L, pot):
    """Recursive function of alghorithm"""
    
    for L2 in pot:
      if L2.IN > L.IN:
        return
      
    illigal_in = set(a for a in L.IN if not a.minus <= L.OUT)
    if illigal_in:
      supperilligal_in = set([a for a in illigal_in if a.minus & (L.UNDEC | (L.IN - illigal_in))])
      if supperilligal_in:
        sii = supperilligal_in.pop()        
        self.__find_prefered(self.__transition_step(sii, L), pot)
      else:
        for ii in illigal_in:
          self.__find_prefered(self.__transition_step(ii, L), pot)
    else:
      #check if L not present in pot (it is implementation specific because labelings are objects)
      for L2 in pot:
        if L2.IN == L.IN and L2.OUT == L.OUT and L2.UNDEC == L.UNDEC:
          return
        
      worse = set(L2 for L2 in pot if L.IN > L2.IN)      
      pot -= worse
      pot.add(L)
        
  def find_prefered(self):
    """Returns all prefered labelings of the argumentation framework"""
    pot = set()
    self.__find_prefered(  Labelling.all_IN(self), pot)
    return pot

  def find_grounded(self):
    """Returns grounded labeling"""
    return Labelling.all_UNDEC(self).up_complete_update()
    
  #sceptical acceptance
  def sceptical_acceptance_proponent(self,d):
    """implements minmax algorithm"""
    for a in d.legal_moves:
      nd = d.__copy__()
      try:        
        nd.argue(a)
      except DiscussionFinished:
        return a
      else:
        if not self.sceptical_acceptance_opponent(nd): return a    
    return None
  
  sceptical_acceptance_opponent = sceptical_acceptance_proponent
  
  def sceptical_acceptance(self, a):
    """checks if argument a is in grounded extension"""
    d = gDiscussion(self)
    try:
      d.argue(a)
    except DiscussionFinished:
      return True
    else:
      return not self.sceptical_acceptance_opponent(d)

  #credulous acceptance
    
  def credulous_acceptance_proponent(self,d):
    """implements minmax algorithm"""

    #if possible repeat your move, it can not make situation worse
    s = d.legal_moves & d.proponent_played
    if s:
      a = s.pop()
      nd = d.__copy__()
      try:
        nd.argue(a)
      except DiscussionFinished:
        return a
      else:
        if not self.credulous_acceptance_opponent(nd):
          return a
        else: return None
    
    for a in d.legal_moves:
      nd = d.__copy__()
      try:
        nd.argue(a)
      except DiscussionFinished:
        return a
      else:
        if not self.credulous_acceptance_opponent(nd):
          return a
    return None

  def credulous_acceptance_opponent(self,d):
    """play available move(s)"""
    #todo: Get rid of this exceptions, it is not handy here
    #toto: Get rid of this for loop, we are plaing just one argument

    s = d.legal_moves & d.proponent_played
    if not s: s = d.legal_moves
    
    for a in s:
      nd = d.__copy__()
      try:
        nd.argue(a)
      except DiscussionFinished:
        return a
      else:
        if not self.credulous_acceptance_proponent(nd):
          return a
        else:
          return None
    return None
    
        
  def credulous_acceptance(self, a):
    """checks if argument a is in grounded extension"""
    d = pDiscussion(self)
    try:
      d.argue(a)
    except DiscussionFinished:
      return True
    else:
      return not self.credulous_acceptance_opponent(d)    
  
  def statusWithWitness(self, a):
    """returns status of given argument and 'witness' eg arguments that existence is needed for proof"""

    witness = []
    status = set()
    if self.sceptical_acceptance(a):
      status.add('IN')
    else:
      witness = [d for d in a.minus if self.sceptical_acceptance(d)]
      if witness: status.add('OUT')
      else:
        status.add('UNDEC')
        if self.credulous_acceptance(a):
          status.add('IN');
        witness = [d for d in a.minus if self.credulous_acceptance(d)]
        if witness:
          status.add('OUT')
    return status, witness

  status = lambda self, a: self.statusWithWitness(a)[0] 
